package 剑指offer.全排列;

import java.util.Arrays;

/**
 * n 是 3 的话
 * 就要打印从 1 到 999 的数
 */
public class 第17题打印从1到最大的n位数 {

    /*
    最简单的方式就是for循环到999
    仔细一想就不对，时间复杂度太高，若给出的n是100，岂不是要输出 1 ~ 99999999........999 那么多个数据？
    无论什么数据类型，一定会溢出的

    所以只能模拟加法

    其实从 1 ~ 999 的输出，就是一个全排列！
    先搞定个位的打印，然后兼顾十位的变化再一次打印一遍个位，然后兼顾百位。。。

    全排列可以用递归实现

    0 0 0 0 0
    0 0 0 0 1
    0 0 0 0 2
      。。。
    0 0 0 1 0
    0 0 0 1 1
    0 0 0 1 2
      。。。
    0 0 0 2 6
    0 0 0 2 7
    0 0 0 2 8
      。。。
    9 9 9 9 9

     */

    public static void print1ToN(int n) {
        if (n <= 0)
            return;
        String[] numbers = new String[n];
        Arrays.fill(numbers, "0");
        // 给高位赋值，数字只能是 0~9
        for (int i = 0; i < 10; i++) {
            numbers[0] = i + "";
            // 处理低位
            printHighNum(numbers, n, 0);
        }
    }

    /**
     *
     * @param numbers 模拟全排列用的数组
     * @param n 最大数据的位数
     * @param index 当前遍历的位数
     */
    private static void printHighNum(String[] numbers, int n, int index) {
        if (index == n - 1) {
            printNumbers(numbers);
            return;
        }
        // 给低位赋值，数字只能是 0~9
        for (int i = 0; i < 10; i++) {
            numbers[index + 1] = i + "";
            printHighNum(numbers, n, index + 1);
        }
    }

    private static void printNumbers(String[] numbers) {
        boolean isBegin0 = true;
        for (int i = 0; i < numbers.length; i++) {
            // 若数组开始的字符是 0 则不打印
            if (isBegin0 && !numbers[i].equals("0")) {
                isBegin0 = false;
            }
            if (!isBegin0) {
                System.out.print(numbers[i]);
            }
        }
    }

    public static void main(String[] args) {
//        print1ToN(1);
        print1ToN(3);
    }

}
